package two.recurtion;

import java.util.ArrayList;
import java.util.List;

/**
 * 组合：
 *      给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
 * 时间复杂度：O(2^n)
 * 思路：组合，递归（边界、本层逻辑、子问题、还原现场）
 */
public class Combine {
    public List<List<Integer>> combine(int n, int k) {
        ans = new ArrayList<List<Integer>>();
        process = new ArrayList<Integer>();
        this.n = n;
        this.k = k;
        findKSubsets(1);
        return ans;
    }
    private void findKSubsets(int index){//递归，去枚举1,2,3,4。。。n这n个数选或者不选
        //选的数已经达到k个 || 把剩下的数全选也不足k个；就可以退出
        if(process.size() > k || process.size() + n - index + 1 < k) return;
        if(index > n){
            ans.add(new ArrayList<Integer>(process));
            return;
        }
        //不选
        findKSubsets(index + 1);
        //选
        process.add(index); //本层逻辑
        findKSubsets(index + 1); //子问题
        process.remove(process.size() - 1); //还原现场
    }

    private List<List<Integer>> ans; //结果集
    private List<Integer> process; //过程结果集
    private int n;
    private int k;
}
